Let $G$ be a plane graph with outer cycle $C$ and let $(L(v):v\in V(G))$ be afamily of non-empty sets. By an $L$-coloring of $G$ we mean a (proper) coloring$\phi$ of $G$ such that $\phi(v)\in L(v)$ for every vertex $v$ of $G$.Thomassen proved that if $v_1,v_2\in V(C)$ are adjacent, $L(v_1)\ne L(v_2)$,$|L(v)|\ge3$ for every $v\in V(C)-\{v_1,v_2\}$ and $|L(v)|\ge5$ for every $v\inV(G)-V(C)$, then $G$ has an $L$-coloring. What happens when $v_1$ and $v_2$ arenot adjacent? Then an $L$-coloring need not exist, but in the first paper ofthis series we have shown that it exists if $|L(v_1)|,|L(v_2)|\ge2$. Here wecharacterize when an $L$-coloring exists if $|L(v_1)|\ge1$ and $|L(v_2)|\ge2$. This result is a lemma toward a more general theorem along the same lines,which we will use to prove that minimally non-$L$-colorable planar graphs withtwo precolored cycles of bounded length are of bounded size. The latter resulthas a number of applications which we pursue elsewhere.
展开▼
机译：令$ G $为具有外循环$ C $的平面图，令$（L（v）：v \ in V（G））$为非空集的族。 $ G $的$ L $着色是指$ G $的（适当）着色$ \ phi $，使得$ G的每个顶点$ v $的$ \ phi（v）\ in L（v）$ $ .Thomassen证明，如果V（C）$中的$ v_1，v_2 \相邻，则V中的每个$ v \ in中的$ L（v_1）\ ne L（v_2）$，$ | L（v）| \ ge3 $ （C）-\ {v_1，v_2 \} $和$ | L（v）| \ ge5 $，每个$ v \ inV（G）-V（C）$，则$ G $具有$ L $着色。 $ v_1 $和$ v_2 $不相邻怎么办？那么就不需要存在$ L $着色了，但是在本系列的第一篇论文中，我们证明了$ | L（v_1）|，| L（v_2）| \ ge2 $时存在。如果$ | L（v_1）| \ ge1 $和$ | L（v_2）| \ ge2 $，则在这里存在$ L $着色时，我们的特征是。这个结果是朝向同一定理的更一般性定理的引理，我们将使用它证明具有两个有限长度的预着色循环的最小非$ L $可着色平面图的边界大小。后者的结果有许多我们在其他地方追求的应用。
展开▼
